RSA Accumulator: Implementations

Repos

Primality test

There is the Fermat primality test 1, but then Carmichael numbers 2 can fool the test (e.g. 561 passes the Fermat primality test but is not prime). So the recommendation is do a one-time untrusted set up and run though all the ids up to 2^40 or more, which passes a Fermat primality test (with base 2) but are not actually prime and then shove this blacklist (which should be fairly small) into a contract and we make part of the primality test be checking against this, which every client can check themselves if they want to.

It seems to me that if we are willing to impose on users the cost of a deterministic “setup” phase that explicitly enumerates ~ 2^40 primes, one alternative would be for the plasma contract to hard-code a merkle root of a depth-40 tree containing the first 2^40 primes, and any transaction that requires a hash-to-prime must provide witnesses into this tree.

BigInt